package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * 最低公共祖先问题
 *
 * @author Mr_wenpan@163.com 2021/12/21 11:06
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode<Integer> head = new TreeNode<Integer>(1);
        head.left = new TreeNode<Integer>(2);
        head.right = new TreeNode<Integer>(3);
        head.left.left = new TreeNode<Integer>(4);
        head.left.right = new TreeNode<Integer>(5);
        head.right.left = new TreeNode<Integer>(6);
        head.right.right = new TreeNode<Integer>(7);
        head.right.right.left = new TreeNode<Integer>(8);
        printTree(head);
        System.out.println("===============");

        TreeNode<Integer> o1 = head.left.right;
        TreeNode<Integer> o2 = head.right.left;

        System.out.println("o1 : " + o1.data);
        System.out.println("o2 : " + o2.data);
        System.out.println("ancestor : " + findLowestCommonAncestor(head, o1, o2).data);
        System.out.println("===============");

    }


    public static TreeNode<Integer> findLowestCommonAncestor(TreeNode<Integer> head, TreeNode<Integer> node1, TreeNode<Integer> node2) {

        if (node1 == null || node2 == null || head == null) {
            return null;
        }

        // 先序遍历二叉树
        // 保存节点的父子关系
        HashMap<TreeNode<Integer>, TreeNode<Integer>> map = new HashMap<>();
        Stack<TreeNode<Integer>> stack = new Stack<>();
        stack.push(head);
        map.put(head, null);
        while (!stack.isEmpty()) {
            TreeNode<Integer> pop = stack.pop();
            if (pop.right != null) {
                stack.push(pop.right);
                map.put(pop.right, pop);
            }
            if (pop.left != null) {
                stack.push(pop.left);
                map.put(pop.left, pop);
            }
        }

        // 再次借助hash表
        HashSet<TreeNode<Integer>> set = new HashSet<>();
        // 随意找一个节点，从该节点一直走到头节点
        while (node1 != null) {
            set.add(node1);
            // 父节点
            node1 = map.get(node1);
        }
        while (node2 != null) {
            // 相遇即是最低公共祖先，类似于单链表相交问题
            if (set.contains(node2)) {
                return node2;
            }
            node2 = map.get(node2);
        }

        return null;
    }

    // for test -- print tree
    public static void printTree(TreeNode<Integer> head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(TreeNode<Integer> head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.data + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        final String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

}
